% TEMPLATE for Usenix papers, specifically to meet requirements of
%  USENIX '05
% originally a template for producing IEEE-format articles using LaTeX.
%   written by Matthew Ward, CS Department, Worcester Polytechnic Institute.
% adapted by David Beazley for his excellent SWIG paper in Proceedings,
%   Tcl 96
% turned into a smartass generic template by De Clarke, with thanks to
%   both the above pioneers
% use at your own risk.  Complaints to /dev/null.
% make it two column with no page numbering, default is 10 point

% Munged by Fred Douglis <douglis@research.att.com> 10/97 to separate
% the .sty file from the LaTeX source template, so that people can
% more easily include the .sty file into an existing document.  Also
% changed to more closely follow the style guidelines as represented
% by the Word sample file. 

% Note that since 2010, USENIX does not require endnotes. If you want
% foot of page notes, don't include the endnotes package in the 
% usepackage command, below.

% This version uses the latex2e styles, not the very ancient 2.09 stuff.
\documentclass[letterpaper,twocolumn,10pt]{article}
\usepackage{usenix,epsfig,endnotes}

\usepackage{times}
\usepackage{graphicx}
%\usepackage{balance}  % for  \balance command ON LAST PAGE  (only there!)
\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{decorations.pathmorphing}
\usetikzlibrary{calc}
\usepackage{subfigure}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
%\usepackage{dingbat}
\usepackage{array}
\usepackage{url}
\usepackage{listings} 
\usepackage{relsize}

\usepackage[T1]{fontenc}
\usepackage[ansinew]{inputenc}

\usepackage[draft]{fixme}
\usepackage{soul}
%\fxsetup{
%    status=draft,
%    author=,
%    layout=inline,
%    theme=color
%}

\lstset{language=Java,
basicstyle=\ttfamily\small
}

%%
\usepackage{titling}
\setlength{\droptitle}{-3em}
\posttitle{\par\end{center}\vspace{-1em}}


\usepackage{titlesec}
\titlespacing{\section}{0pt}{*1.0}{*1.0}
\titlespacing{\subsection}{0pt}{*1.0}{*1.0}
\titlespacing{\subsubsection}{0pt}{*1.0}{*1.0}
\titlespacing{\paragraph}{0pt}{*1.0}{*1.0}
%%%

\usepackage%[small,bf]
{caption}
\setlength{\abovecaptionskip}{2mm}
\setlength{\belowcaptionskip}{-4mm}
\setlength{\floatsep}{8mm}

\definecolor{fxnote}{rgb}{0.8000,0.0000,0.0000}
% define the background colour:
\colorlet{fxnotebg}{yellow}


\setcounter{tocdepth}{3}

\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}

\newcommand{\name}{LOOM}
\newcommand{\fullname}{Lightweight Optimal Overlay Mechanism}

\newcommand{\tightitem}{\vspace{-2mm}\item}




\begin{document}

%don't want date printed
\date{}

%make title bold and 14 pt font (Latex default is non-bold, 16 pt)
\title{\Large \bf \name: Optimal Aggregation Overlays for In-Memory Big Data Processing\thanks{Financially supported by DARPA grant \# N11AP20014, Purdue Research Foundation grant \# 205434, and Google Award ``Geo-Distributed Big Data Processing''.}}
%for single author (just remove % characters)
\author{
{\rm William Culhane~~~~Kirill Kogan~~~~Chamikara Jayalath~~~~Patrick Eugster}\\
Department of Computer Science,  Purdue University
% copy the following lines to add more authors
% \and
% {\rm Name}\\
%Name Institution
} % end author

\maketitle

% Use the following at camera-ready time to suppress page numbers.
% Comment it out when you first submit the paper for review.
%\thispagestyle{empty}


\subsection*{Abstract}
Aggregation underlies the distillation of information from big data. Many
well-known basic operations including top-$k$ matching and word count 
hinge on fast aggregation across large data-sets. Common frameworks including
MapReduce support aggregation, but do not explicitly consider or optimize it.
Optimizing aggregation however becomes yet more relevant in recent ``online'' approaches to
expressive big data analysis which store data in main memory across nodes. This shifts the bottlenecks from disk I/O to distributed computation and network communication and significantly increases the impact of
aggregation time on total job completion time.

This paper presents \name, a (sub)system for efficient big data aggregation for use 
within big data analysis frameworks. \name\ efficiently
supports two-phased (sub)computations consisting in a first phase
performed on individual data sub-sets (e.g., word count, top-$k$
matching) followed by a second aggregation phase which consolidates individual
results of the first phase (e.g., count sum, top-$k$). Using characteristics of
an aggregation function, \name\ constructs a specifically configured
aggregation overlay to minimize aggregation costs. 
 We present optimality heuristics and experimentally demonstrate the benefits of thus optimizing
aggregation overlays using microbenchmarks and real world examples.

%This paper considers the configurable variables of an aggregation overlay which
%affect the time required to aggregate. We lay out the assumptions and a basic
%model for problems which allows optimization of these variables. We present
%optimality heuristics and experimentally demonstrate the effects of optimizing
%aggregation overlays using targeted microbenchmarks.\fixme{shd make it more systems-ish}

\input{HCintro}


\input{HCmodel}

\input{HCarchitecture}

\input{HCresults}

\input{HCrelated}


\input{HCconclusions}

%{\footnotesize 
%\newcommand{\mynegbibspace}{\vspace{-1.5mm}}
%\input{final.bbl} }


{\footnotesize \bibliographystyle{acm}%plain}
\bibliography{references}

\end{document}







